import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/21 20:16
 */
public class 字典树_并查集 {

    private int[][] direct = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


    /*
     * #problem 212 单词搜索II
     * */
    // 1. 回溯 --> 超时
    private Set<String> res = new HashSet<>();

    public List<String> findWords(char[][] board, String[] words) {
        Set<String> dict = new HashSet<>(Arrays.asList(words));
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                StringBuilder sb = new StringBuilder();
                sb.append(board[i][j]);
                visited[i][j] = true;
                findWordsDFS(board, i, j, dict, sb, visited);
                visited[i][j] = false;
            }
        }

        return new ArrayList<>(res);
    }

    private void findWordsDFS(char[][] board, int x, int y, Set<String> words, StringBuilder sb, boolean[][] visited) {
        String word = sb.toString();
        if (words.contains(word)) {
            res.add(word);
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + direct[i][0];
            int ty = y + direct[i][1];
            if (tx < 0 || ty < 0 || tx >= board.length || ty >= board[0].length || visited[tx][ty]) {
                continue;
            }
            visited[tx][ty] = true;
            sb.append(board[tx][ty]);
            findWordsDFS(board, tx, ty, words, sb, visited);
            visited[tx][ty] = false;
            sb.delete(sb.length() - 1, sb.length());
        }
    }

    // 2. 回溯 + 字典树加速
    @Test
    void findWordsTest() {
        findWords2(new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}
                , new String[]{"oath", "pea", "eat", "rain"});
    }

    private class Trie2 {
        String word;
        Map<Character, Trie2> children;

        public Trie2() {
            children = new HashMap<>();
        }

        public void insert(String word) {
            Trie2 node = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                Trie2 nextNode = node.children.get(c);
                if (nextNode == null) {
                    nextNode = new Trie2();
                    node.children.put(c, nextNode);
                }
                node = nextNode;
            }
            node.word = word;
        }
    }

    public List<String> findWords2(char[][] board, String[] words) {
        Trie2 root = new Trie2();
        for (String word : words) {
            root.insert(word);
        }
        int n = board.length, m = board[0].length;
        boolean[][] visited = new boolean[n][m];
        Set<String> res = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                findWords2DfsAndTrie(board, i, j, res, root, visited);
            }
        }
        return new ArrayList<>(res);
    }

    private void findWords2DfsAndTrie(char[][] board, int x, int y, Set<String> res, Trie2 parent, boolean[][] visited) {
        char c = board[x][y];
        if (!parent.children.containsKey(c)) {
            // 字典树中没有以该字符开头的单词
            return;
        }
        Trie2 nowTrie = parent.children.get(c);
        if (nowTrie.word != null && !"".equals(nowTrie.word)) {
            res.add(nowTrie.word);
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int tx = x + direct[i][0];
            int ty = y + direct[i][1];
            if (tx < 0 || ty < 0 || tx >= board.length || ty >= board[0].length || visited[tx][ty]) {
                continue;
            }
            findWords2DfsAndTrie(board, tx, ty, res, nowTrie, visited);
        }
        visited[x][y] = false;
    }


    /*
     * #problem 1268 搜索推荐系统
     * */
    // 1. 字典树（前缀树）
    private class Trie3 {
        // 标识是否为单词结尾
        String word;
        Map<Character, Trie3> children;

        public Trie3() {
            children = new HashMap<>();
        }

        public Trie3 searchNode(String word) {
            Trie3 node = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!node.children.containsKey(c)) {
                    return null;
                }
                node = node.children.get(c);
            }
            return node;
        }

        public void insert(String word) {
            Trie3 node = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new Trie3());
                }
                node = node.children.get(c);
            }
            node.word = word;
        }

        public List<String> getAllSubWord() {
            List<String> res = new ArrayList<>();
            if (word != null && !"".equals(word)) {
                res.add(word);
            }
            if (children.isEmpty()) {
                return res;
            }
            for (char c = 'a'; c <= 'z'; c++) {
                if (res.size() >= 3) {
                    break;
                }
                if (!children.containsKey(c)) {
                    continue;
                }
                Trie3 child = children.get(c);
                res.addAll(child.getAllSubWord());
            }
            return res.size() > 3 ? res.subList(0, 3) : res;
        }

    }

    @Test
    void suggestedTest() {
        suggestedProducts(new String[]{"mobile", "mouse", "moneypot", "monitor", "mousepad"}, "mouse");
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> res = new ArrayList<>();
        Trie3 root = new Trie3();
        for (String product : products) {
            root.insert(product);
        }
        StringBuilder sb = new StringBuilder();
        for (char c : searchWord.toCharArray()) {
            sb.append(c);
            Trie3 trie = root.searchNode(sb.toString());
            if (trie != null) {
                res.add(trie.getAllSubWord());
            } else {
                res.add(new ArrayList<>());
            }
        }
        return res;
    }

    // 2. 字典序排序 + 二分查找 TODO



    /*
     * #problem 130 被围绕的区域
     * */

    // 1. DFS
    public void solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            int x = i;
            int y1 = 0, y2 = board[0].length - 1;
            if (board[x][y1] == 'O') {
                board[x][y1] = '1';
                solveF(board, x, y1);
            }
            if (board[x][y2] == 'O') {
                board[x][y2] = '1';
                solveF(board, x, y2);
            }
        }
        for (int i = 0; i < board[0].length; i++) {
            int x1 = 0, x2 = board.length - 1;
            int y = i;
            if (board[x1][y] == 'O') {
                board[x1][y] = '1';
                solveF(board, x1, y);
            }
            if (board[x2][y] == 'O') {
                board[x2][y] = '1';
                solveF(board, x2, y);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '1') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void solveF(char[][] board, int x, int y) {
        for (int i = 0; i < direct.length; i++) {
            int tx = x + direct[i][0];
            int ty = y + direct[i][1];
            if (tx < 0 || ty < 0 || tx >= board.length || ty >= board[0].length || board[tx][ty] != 'O' || board[tx][ty] == '1') {
                continue;
            }
            board[tx][ty] = '1';
            solveF(board, tx, ty);
        }
    }

    // 2. 并查集实现
    public void solve2(char[][] board) {
        int n = board.length, m = board[0].length;
        UnionFind find = new UnionFind(n * m + 1);
        // 与 边界O连接的区域
        int dymmyNode = n * m;
        int[][] direct = new int[][]{{1, 0}, {0, 1}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {
                    if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                        find.union(i * m + j, dymmyNode);
                    }
                    for (int[] d : direct) {
                        int tx = i + d[0];
                        int ty = j + d[1];
                        if (tx < 0 || ty < 0 || tx >= n || ty >= m || board[tx][ty] == 'X') {
                            continue;
                        }
                        find.union(i * m + j, tx * m + ty);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (find.find(i * m + j) != find.find(dymmyNode)) {
                    board[i][j] = 'X';
                }
            }
        }

    }

    /*
     * #problem 200 岛屿数量
     * */
    // 1. 并查集实现
    private class UnionFind {
        public int count;
        public int[] parent;

        public UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootQ != rootP) {
                parent[rootQ] = rootP;
                count--;
            }
        }
    }

    public int numIslands(char[][] grid) {
        // 判断右边和下边即可 （左边和上面的已经处理过了）
        int[][] direct = new int[][]{{1, 0}, {0, 1}};
        // 初始化并查集
        int n = grid.length, m = grid[0].length;
        UnionFind unionFind = new UnionFind(n * m);
        int water = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') {
                    water++;
                } else {
                    for (int[] d : direct) {
                        int tx = i + d[0];
                        int ty = j + d[1];
                        if (tx < n && ty < m && grid[tx][ty] == '1') {
                            unionFind.union(i * m + j, tx * m + ty);
                        }
                    }
                }
            }
        }
        return unionFind.count - water;
    }

    /*
     * #problem 547 省份数量
     * */
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || isConnected[i][j] == 0) {
                    continue;
                } else {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.count;
    }
}

/*
 * #problem 208 实现Trie(前缀树)
 * */
class Trie {

    private TrieNode root;

    private class TrieNode {
        public boolean end;
        public Map<Character, TrieNode> paths;

        public TrieNode() {
            paths = new HashMap<>();
        }
    }

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode nextNode = node.paths.get(c);
            if (nextNode == null) {
                nextNode = new TrieNode();
                node.paths.put(c, nextNode);
            }
            node = nextNode;
        }
        node.end = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode nextNode = node.paths.get(c);
            if (nextNode == null) {
                return false;
            }
            node = nextNode;
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            TrieNode nextNode = node.paths.get(c);
            if (nextNode == null) {
                return false;
            }
            node = nextNode;
        }
        return true;
    }

}
